package 动态规划;

public class No72编辑距离 {

    /**
     * 给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
     * 你可以对一个单词进行如下三种操作：
     * 插入一个字符
     * 删除一个字符
     * 替换一个字符
     *  
     * 示例 1：
     * 输入：word1 = "horse", word2 = "ros"
     * 输出：3
     * 解释：
     * horse -> rorse (将 'h' 替换为 'r')
     * rorse -> rose (删除 'r')
     * rose -> ros (删除 'e')
     * 示例 2：
     * 输入：word1 = "intention", word2 = "execution"
     * 输出：5
     * 解释：
     * intention -> inention (删除 't')
     * inention -> enention (将 'i' 替换为 'e')
     * enention -> exention (将 'n' 替换为 'x')
     * exention -> exection (将 'n' 替换为 'c')
     * exection -> execution (插入 'u')
     */

    /**
     * 解法在本子上
     */
    public int minDistance(String word1, String word2) {

        if(word1.length()==0){
            return word2.length();
        }

        if(word2.length()==0){
            return word1.length();
        }

        int[][] dp=new int[word1.length()][word2.length()];

        if(word1.charAt(0)!=word2.charAt(0)){
            //不等于,则需要换
            dp[0][0]=1;
        }

        //base注意项:相等全删然后比较
        //维护好第一排
        for (int j = 1; j < word2.length(); j++) {
            if(word2.charAt(j)!=word1.charAt(0)){
                //插入即可
                dp[0][j]=dp[0][j-1]+1;
            }else{
                //相等,全删然后比较
                dp[0][j]=Math.min(j,dp[0][j-1]+1);
            }
        }

        //维护好第一列
        for (int i = 1; i < word1.length(); i++) {
            if(word1.charAt(i)!=word2.charAt(0)){
                //插入即可
                dp[i][0]=dp[i-1][0]+1;
            }else{
                //相等,全删然后比较
                dp[i][0]=Math.min(i,dp[i-1][0]+1);
            }
        }

        for (int i = 1; i < word1.length(); i++) {
            for (int j = 1; j < word2.length(); j++) {
                if(word1.charAt(i)==word2.charAt(j)){
                    dp[i][j]=dp[i-1][j-1];
                }else{
                    dp[i][j]=Math.min(dp[i-1][j],Math.min(dp[i][j-1],dp[i-1][j-1]))+1;
                }
            }
        }

        return dp[word1.length()-1][word2.length()-1];
    }

    public static void main(String[] args) {
        No72编辑距离 n=new No72编辑距离();
        int result = n.minDistance("intention", "execution");
        System.out.println(result);
    }

}
